1. Field of the Invention
The present invention relates to the field of cache memory system. More particularly, the present invention relates to reducing cache flushes in a virtual cache memory system that supports alias addressing for programs with common memory and employs write through with no write allocate for updating the cache and main memory.
2. Background
In a cache memory system that employs write through with no write allocate for updating the cache and main memory, data are dispatched to a cache line of the cache memory and the corresponding memory block of the main memory at the same time. However, the data are written into the cache line only if there is a write cache hit. The alternative is the write through with write allocate approach which loads the memory block into the cache line, and then updates the cache line as if it was a write cache hit.
Additionally, the writing of the data into the corresponding memory block typically takes a lot longer than the writing of the data into the cache line of the cache memory. While waiting for the writing of the data into main memory to complete, the central processing unit (CPU) is stalled. One approach to reduce write stalls is to employ a write buffer for writing into the main memory, thereby allowing the CPU to continue after the data is written into the cache memory.
In a virtual cache memory system, cache hit/miss is decided based on the virtual address (plus other information) instead of the physical address. Typically, to access the main memory, the virtual address is translated into the physical address by a memory management unit. For a cache memory system having a size greater than one physical page, two or more virtual addresses may be translated into the same physical address. In other words, data from the same physical address may be cached in two or more distinct lines.
This characteristic of having a physical address mapped into two or more virtual addresses, except the fact that the content of the physical address is cached into two or more cache lines, is actually desirable to executing programs who want to share a common memory. Each program sharing the common memory will have their own virtual addresses for the common memory, commonly referred to as alias addressing. However, the fact that the content of the physical address is cached into two or more cache lines presents a data consistency problem, since the content in the cache lines can get out of sync when the content of one of the cache lines is updated in a write cache hit. One approach to the data consistency problem of alias addressing is to employ a technique that forces the virtual addresses to be cached into the same cache location. For those virtual addresses that cannot be forced into the same cache location, their physical memory page is marked as "Do Not Cache", thereby avoiding the data consistency problem all together.
In a virtual cache memory system that employs write through with no write allocate for updating the cache and main memory, the data consistency problem of alias addressing is still not fully addressed, since data can be written around the common cache location into the physical location directly on a write cache miss. To ensure data consistency, the cache line is flushed on a write cache miss, that is the content of the cache line is invalidated on a write cache miss. Typically, the cache line is unconditionally flushed, even though flushing of the cache line is unnecessary for a virtual address that map to a physical address of a "Do Not Cache" physical memory page, and most programs do not share common memory. Flushing the line is the preferred method because it is very difficult for hardware to determine which virtual addresses from the CPU are aliased. Hence, a general rule is to assume they all are and flush unconditionally.
Flushing a cache line is costly, since the content of the cache line that was invalidated would have to be refetched from the main memory later. Unconditional flushing is particularly wasteful since flushing is unnecessary for those virtual addresses that map to "Do Not Cache" physical addresses, and yet these unnecessary flushings will always be performed since these virtual addresses always result in write cache misses. In a typical computer system that supports alias addressing for programs with common memory, there are lots of physical addresses that are marked "Do Not Cache". For example, the memory allocated for the frame buffers of such a computer system having a pixmapped video display and/or display adapters are typically marked "Do Not Cache". Every screen scroll performed by the processor will cause unnecessary flushings to be performed, since every write to a frame buffer will cause a write cache miss.
Experience has shown that excessive flushing can dramatically hurt the performance of such computer systems, particularly if the virtual cache memory system is directly mapped or mapped with a low set associativity. Therefore, it is desirable if flushing of a cache line can be performed conditionally when a cache write miss occurs on a virtual cache memory system that supports alias addressing for programs with common memory and employs write through with no write allocate for updating the cache and main memory.
For further descriptions of virtual cache memory system and write through with no write allocate, see J. L. Hennessy, D. A. Patterson, Computer Architecture, A Quantitative Approach, Morgan Kaufmann Publishers Inc., 1990, pages 408-449. For further descriptions of alias addressing, see U.S. patent application Ser. No. 07/104,635, filed on Oct. 10, 1987, abandoned, and its Continuation application Ser. No. 07/554,186, filed on Jul. 16, 1990 and issued as a U.S. Pat. No. 5,119,290.